package org.datacoder.geocoding.datastructures.points

import org.datacoder.geocoding.datastructures.geoshapes.*
import org.datacoder.geocoding.datastructures.util.*
import org.datacoder.geocoding.jurisdiction.*

class LayeredRangeTreeSortedArray implements PointsWithinRectangleFinder {

    LayeredRangeTreeSortedArrayNode root

    public LayeredRangeTreeSortedArray(Collection<Jurisdiction> jurisdictions){
        if(jurisdictions.size() == 0){      // Unnecessary.  However, keeps bootstrap
            return                          // from throwing fit with empty db.
        }
        List<GeoPoint> geoPointsList = new ArrayList<GeoPoint>()
        for(juris in jurisdictions){
            geoPointsList.add(juris.toGeoPoint())
        }
        GeoPoint[] geoPoints = geoPointsList.toArray()
        Arrays.sort(geoPoints, new GeoPointComparator(GeoShape.LON))
        root = createNode(geoPoints, 0, geoPoints.length)
    }

    public LayeredRangeTreeSortedArrayNode createNode(GeoPoint[] geoPoints, int startIndex, int endIndex){
        LayeredRangeTreeSortedArrayNode lrtsaNode = new LayeredRangeTreeSortedArrayNode()
        int middle = (startIndex + endIndex)/2
        lrtsaNode.lonDiscriminator = geoPoints[middle].lon
        lrtsaNode.minLon = geoPoints[startIndex].lon
        lrtsaNode.maxLon = geoPoints[endIndex - 1].lon

        Set<Jurisdiction> jurisdictions = new HashSet<Jurisdiction>()
        for(int i = startIndex; i < endIndex; i++){
            jurisdictions.add(geoPoints[i].juris)
        }
        lrtsaNode.geoPointsByLat = new SortedArray(jurisdictions, GeoShape.LAT)

        if(startIndex < middle){
            lrtsaNode.left = createNode(geoPoints, startIndex, middle)
        }
        if((middle + 1) < endIndex){
            lrtsaNode.right = createNode(geoPoints, middle, endIndex)
        }
        return lrtsaNode
    }

    public Set<Jurisdiction> findPointsWithinRectangle(GeoRectangle gr){
        Set<Jurisdiction> jurisdictions = new HashSet<Jurisdiction>()
        Queue<LayeredRangeTreeSortedArrayNode> lrtsaNodeQueue = new LinkedList<LayeredRangeTreeSortedArrayNode>()
        lrtsaNodeQueue.offer(root)
        while(lrtsaNodeQueue.peek() != null){
            LayeredRangeTreeSortedArrayNode currentNode = lrtsaNodeQueue.poll()
            if(gr.containsInterval(GeoShape.LON, currentNode.minLon, currentNode.maxLon)){
                currentNode.geoPointsByLat.findPointsWithinInterval(gr.toGeoInterval(GeoShape.LAT), jurisdictions)
            }else{
                if((currentNode.left != null) && (gr.lon1 <= currentNode.lonDiscriminator)){
                    lrtsaNodeQueue.offer(currentNode.left)
                }
                if((currentNode.right != null) && (currentNode.lonDiscriminator <= gr.lon2)){
                    lrtsaNodeQueue.offer(currentNode.right)
                }
            }
        }
        return jurisdictions
    }

}

